package com.wangp.mywrite.s_algorithm.recursion;

/***
 * @author wangpeng
 * @since 2022-03-10  10:25
 */
public class Fibonacci {

    private static long normalFibonacci(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        return normalFibonacci(n - 1) + normalFibonacci(n - 2);
    }

    private static long tailCallFibonacci(int n, long value, long result) {
        if (n == 1) {
            return result;
        }
        return tailCallFibonacci(n - 1, result, value + result);
    }

    private static long foreachFibonacci(int n) {
        long result = 0;
        long f0 = 0;
        long f1 = 1;
        for (int i = 2; i <= n; i++) {
            result = f0 + f1;
            f0 = f1;
            f1 = result;
        }
        return result;
    }

    private static void printFibonacci() {
        long timeMillis = System.currentTimeMillis();
        System.out.println(normalFibonacci(50));
        long end = System.currentTimeMillis();
        System.out.println("普通递归耗时：" + (end - timeMillis));
        System.out.println(tailCallFibonacci(50, 0, 1));
        timeMillis = System.currentTimeMillis();
        System.out.println("尾递归耗时：" + (timeMillis - end));
        System.out.println(foreachFibonacci(50));
        end = System.currentTimeMillis();
        System.out.println("循环递归耗时：" + (end - timeMillis));
    }

    public static void main(String[] args) {
//        printFibonacci();
        long timeMillis = System.currentTimeMillis();
        System.out.println(factorial(10));
        long end = System.currentTimeMillis();
        System.out.println("普通阶乘耗时：" + (end - timeMillis));
        System.out.println(tailFactorial(10, 1));
        timeMillis = System.currentTimeMillis();
        System.out.println("尾递归耗时：" + (timeMillis - end));

    }


    private static long factorial(int n) {
        if (n == 1) {
            return n;
        }
        return n * factorial(n - 1);
    }

    private static long tailFactorial(int n, long total) {
        if (n == 1) {
            return total;
        }
        return tailFactorial(n - 1, total * n);
    }
}
